/*
 * @lc app=leetcode.cn id=501 lang=cpp
 *
 * [501] 二叉搜索树中的众数
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
  vector<int> ans;
  int num, cnt, max;
  vector<int> findMode(TreeNode* root)
  {
    cnt = max = 0;
    DFS(root);
    if (cnt == max)
      ans.push_back(num);
    if (cnt > max)
      return {num};
    return ans;
  }

  void DFS(TreeNode* root)
  {
    if (root) {
      DFS(root->left);
      if (cnt == 0) { // 第一个值
        num = root->val;
        cnt = max = 1;
      }
      else {
        if (num == root->val)
          ++cnt;
        else {
          // 添加上一个不一样的数
          if (cnt == max)
            ans.push_back(num);
          else if (cnt > max) {
            ans.clear(); // 清空ans;
            max = cnt; // 更新最大出现次数
            ans.push_back(num); // 将num添加到ans;
          }
          num = root->val;
          cnt = 1;
        }
      }
      DFS(root->right);
    }
  }
};
// @lc code=end
